import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-10-14
 * Time:16:05
 */

/**
 * 汉诺塔问题
 */

public class hanota {
    public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {

        dfs(a,b,c,a.size());
    }
    public void dfs(List<Integer> a, List<Integer> b, List<Integer> c,int n){
        if (n == 1){
            // 把 a 柱子的最后一个盘子移动到c
            c.add(a.remove(a.size() - 1));
            return;
        }
        // 把 a 上的 n-1 个盘子移动到b上
        dfs(a,c,b,n-1);
        // 把 a 的最上面的那个盘子放到 c 上
        c.add(a.remove(a.size() - 1));
        // 把 b 上 n-1 个盘子通过 a 放到 c 上
        dfs(b,a,c,n-1);
    }
}
